package algorithm_demo.demo04;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.cn/problems/longest-word-lcci/comments/
 *
 * @author Api
 * @date 2023/2/19 10:35
 */
public class Code10_LongestWord {
    /*
    给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。
    若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
    示例：

    输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
    输出： "dogwalker"
    解释： "dogwalker"可由"dog"和"walker"组成。
    提示：

    0 <= len(words) <= 200
    1 <= len(words[i]) <= 100
    */

    public static void main(String[] args) {
        String[] words = new String[]{"cat","banana","dog","nana","walk","walker","dogwalker"};
        System.out.println(longestWord(words));
    }
    public static String longestWord(String[] words) {
        Arrays.sort(words, (o1, o2) -> {
            if (o1.length() == o2.length()) {
                return o1.compareTo(o2);
            } else {
                return Integer.compare(o2.length(), o1.length());
            }
        });
        //把数组做成set，提高检测的效率
        Set<String> set = new HashSet<>(Arrays.asList(words));
        //遍历检测当前单词是不是组合单词，是的话直接返回
        for (String word : words) {
            set.remove(word);
            if (isComposeWord(set, word)) {
                return word;
            }
            set.add(word);
        }
        return "";
    }

    //检测word是否由set里面的单词组成
    public static boolean isComposeWord(Set<String> set, String word) {
        if (word.length() == 0) {
            return true;
        }
        for (int i = 0; i < word.length(); i++) {
            //前半部分+后半部分
            if (set.contains(word.substring(0,i+1)) && isComposeWord(set, word.substring(i+1))){
                return true;
            }
        }
        return false;
    }
}
